package org.example.algorithm.backtracking;

import java.util.ArrayList;
import java.util.List;

/**
 * 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
 */
public class GenerateParenthesisSolution {

    public List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<>();
        if (n == 0) {
            return res;
        }
        StringBuilder sb = new StringBuilder();
        doGenerate(res, sb, 2*n, 0, 0);
        return res;
    }

    private void doGenerate(List<String> res, StringBuilder sb, int total, int leftCount, int rightCount) {
        if (leftCount + rightCount == total) {
            res.add(sb.toString());
        } else if (leftCount + rightCount < total){
            int diff = leftCount - rightCount;
            int left = total - leftCount - rightCount;
            if (diff == left) {
                for (int i=0;i<diff;i++) {
                    sb.append(')');
                }
                doGenerate(res, sb, total, leftCount, rightCount+diff);
                for (int i=0;i<diff;i++) {
                   sb.deleteCharAt(total-i-1);
                }
            } else if (diff < left) {
                sb.append('(');
                doGenerate(res, sb, total, leftCount+1, rightCount);
                sb.deleteCharAt(leftCount+rightCount);
                if (rightCount < leftCount) {
                    sb.append(')');
                    doGenerate(res, sb, total, leftCount, rightCount+1);
                    sb.deleteCharAt(leftCount+rightCount);
                }
            }
        }
    }

    public static void main(String[] args) {
        GenerateParenthesisSolution solution = new GenerateParenthesisSolution();
        List<String> res = solution.generateParenthesis(3);
        System.out.println(res);
    }
}
